package 回溯;

import java.util.*;

public class q491非递减子序列保持相对位置关系 {

    public static void main(String[] args) {

        int[] nums = {1,4,6,7,8,1,1,1};
        Solution solution = new q491非递减子序列保持相对位置关系().new Solution();
        solution.findSubsequences(nums);
    }
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> findSubsequences(int[] nums) {

            backtracking(nums,0);
            return res;
        }
        void backtracking(int[] nums, int startIndex){
            if( path.size()>1){
                //path倒转
                List<Integer> list = new ArrayList<>(path);
                Collections.reverse(list);
                res.add(list);
            }
            HashSet<Integer> hs = new HashSet<>(); // 记录本层元素使用情况，去重
            for(int i = startIndex ; i < nums.length; i++){
                if(hs.contains(nums[i])){
                    continue;
                }
                if(path.size()==0 || nums[i]>=path.peek()){
                    hs.add(nums[i]);
                    path.push(nums[i]);
                    backtracking(nums,i+1);
                    path.pop();
                }
            }



        }
    }
}
